package com.ruoxi.blog.test;

import java.util.ArrayList;
import java.util.List;

/**
	* @author YaoXian
	* @title: Queen8
	* @projectName ruoxi-blog
	* @description: 若兮微服务 - 递归回溯算法 - 解决8皇后问题
	*                            对应力扣回溯算法章节, 困难第一题
	* @date 2021-03-08 13:57
	*/
public class Queen8 {
		/**
			* 8个皇后
			*/
		private static int max = 8;
		
		/**
			* 递归调用机制 : 基本数据类型传值, 引用数据类型传引用,故全局共享一个数组
			* 使用一维数组表示棋盘,数组的索引,相当于第几行
			* 索引对应的具体数值,代表第几列
			* 举例: map = {2,1,2} 索引0的值为2, 代表第一个皇后放在第1行,第3列
			*/
		private static int [] map = new int[max];
		
		private static int count = 0;
		
		private static List<List<String>> lists = new ArrayList<List<String>>();
		
		public static void main(String[] args) {
				/**
					* n=0时,代表从第一个皇后开始摆起
					*/
				Queen8.check(0);
				System.out.println("一共有"+count+"种解法");
				System.out.println(lists.size());
		}
		
		public static void check(int n){
				/**
					* 如果n=8,代表8个皇后摆放完毕,跳出当前递归栈,返回上一个栈,并调用打印方法
					* 8个皇后摆放完毕, 即代表找到一次正确摆放方法
					*/
				if (n == 8){
						print();
						return;
				}
				/**
					* 0-7的for循环,代表将当前n对应的皇后,
					* 从第1列摆到第8列,一直检查是否冲突
					*/
				for (int i = 0; i < max; i++) {
						map[n] = i;
						/**
							* 每次摆放调用judge方法,如果不冲突,递归调用check方法,传入的参数+1
							* 代表摆放下一个皇后,此时,递归进入下一个栈, 当前栈的for循环并未
							* 执行完毕,例如,当i=0时候,就检查到不冲突, 后面都没有执行,但不代表
							* 不执行,而是当上一个递归栈退出后, 才会回溯执行该栈的for循环,
							* 执行for循环, 就代表开始重新摆放原来皇后的位置了, 这就体现了回溯
							*/
						if (judge(n)){
								check(n+1);
						}
				}
		}
		
		public static boolean judge(int n){
				/**
					* 每次摆放一个皇后, 会和前面所有皇后比较是否冲突,故i < n
					* 举例: 摆放第8个皇后,即n=7,i<7,会和前面7个皇后比较是否冲突
					*/
				for (int i = 0; i < n; i++) {
						/**
							* map[i] == map[n] :代表在同一列,前面创建数组时提到过,
							* 值代表所在列,如果值相等,代表在同一列
							* Math.abs(n-i) == Math.abs(map[n]-map[i]) :代表在同一斜线,
							* 索引之差的绝对值,代表行之间的距离,对应的值之差的绝对值,
							* 代表列之间的距离,如果行列之间的距离相等,根据数学规律,两个在同一条斜线上
							*/
						if (map[i] == map[n] || Math.abs(n-i) == Math.abs(map[n]-map[i])){
								return false;
						}
				}
				return true;
		}
		
		public static void print(){
				/**
					* 每次调用一次print方法,代表找到一次正确摆法
					*/
				count++;
				ArrayList<String> arrayList = new ArrayList<String>();
				for (int i = 0; i < max; i++) {
						System.out.print(map[i] + " ");
						arrayList.add(String.valueOf(map[i]));
				}
				lists.add(arrayList);
				System.out.println();
		}
		
}
